import java.util.ArrayList;
import java.util.List;

/**
 * @Author: YCKOKO
 * @Date: 2023-04-05
 * @Time:20:33
 * @Description:邻接表
 */
public class Graph2 {
    class Node{
        private String start;
        private String end;
        private int weight;
        private Node next;

        public Node(String start, String end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    private boolean isDirect;
    private ArrayList<Node> edgeList; //邻接表，
    private List<String> vertexList;
    private int numOfEdges;


    public Graph2(int num,boolean isDirect) {
         edgeList = new ArrayList<>(num);
         vertexList = new ArrayList<>(num);
        for (int i = 0; i < num; i++) {
            edgeList.add(null);
        }
        this.isDirect = isDirect;
        numOfEdges = 0;
    }

    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    public void insertEdge(String v1,String v2,int weight){
        if(isDirect){
            insertEdgeChild(v1,v2,weight);
        }else{
            insertEdgeChild(v1,v2,weight);
            insertEdgeChild(v2,v1,weight);
        }
        numOfEdges++;
    }

    public void insertEdgeChild(String v1,String v2,int weight){
        int start = getIndexOfVertex(v1);
        Node cur = edgeList.get(start);
        while(cur != null){
            if(cur.end == v2){
                return;
            }
            cur = cur.next;
        }
        Node node = new Node(v1,v2,weight);
        node.next = edgeList.get(start);
        edgeList.set(start,node);
    }


    public int getIndexOfVertex(String vertex){
        return vertexList.indexOf(vertex);
    }

    public int getDivOfVertex(String vertex){
        int index = getIndexOfVertex(vertex);
        Node cur = edgeList.get(index);
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        if(isDirect){
            for (int i = 0; i <verticesSize(); i++) {
                if(index == i){
                    continue;
                }else{
                    Node temp = edgeList.get(i);
                    while(temp != null){
                        if(temp.end == vertexList.get(index)){
                            count++;
                        }
                        temp = temp.next;
                    }
                }
            }
        }
        return count;
    }

    public void showGraph(){
        for (int i = 0; i < verticesSize(); i++) {
            System.out.print(vertexList.get(i) + "->");

            Node cur = edgeList.get(i);
            while(cur != null){
                System.out.print(cur.end+"->");
                cur = cur.next;
            }
            System.out.println("null");
        }
    }

    public int verticesSize() {
        return vertexList.size();
    }

    public int edgesSize() {
        return numOfEdges;
    }


    public static void main(String[] args) {
        Graph2 graph = new Graph2(5,false);
        String[] vertexs = {"v0","v1","v2","v3","v4"};
        for (String vertex: vertexs) {
            graph.insertVertex(vertex);
        }

        graph.insertEdge("v0","v4",6);
        graph.insertEdge("v1","v0",9);
        graph.insertEdge("v1","v2",3);
        graph.insertEdge("v2","v0",2);
        graph.insertEdge("v2","v3",5);
        graph.insertEdge("v3","v4",6);

        graph.showGraph();
        System.out.println(graph.getDivOfVertex("v4"));

        System.out.println(graph.numOfEdges);

    }

}
